1. Field of the Invention
This invention relates to devices and methods for routing digital communications, and more particularly to devices and methods utilizing crossproducting as an efficient caching strategy.
2. Description of the Prior Art
Internet traffic is exploding both because of a growing number of users and an increasing demand for bandwidth intensive data. While email only contributes small change, big-ticket items such as video and images can easily require megabytes of data to be transferred. To keep up with increased traffic, the speed of links in the Internet core has been increased from 45 MBPS to 155 MBPS, and established vendors as well as many startups are working to build faster routers that can handle Gigabit (1000 million bits per second) links. Thus there is a major market opportunity for high performance routers.
A traditional router that forwards a message has two major tasks: first, looking up of the message""s destination address in the router database; and second, internally transferring the message to one of many possible output links. The second task is well understood with most vendors using fast busses or crossbar switches. In the last year, several new solutions have appeared to the message lookup problem as well. Thus there appears to be no impediment to building and selling gigabit routers for data forwarding in the Internet.
Increasingly, however, users are demanding, and some router vendors are providing, a more discriminating form of forwarding called xe2x80x9clayer 4 forwardingxe2x80x9d in which routing decisions can be based on higher level headers. In traditional terminology, link headers are called xe2x80x9clayer 2 headersxe2x80x9d and routing headers are called xe2x80x9clayer 3 headers.xe2x80x9d The protocols that ensure reliable delivery use what are known as xe2x80x9clayer 4 headers,xe2x80x9d while applications such as email use what are known as xe2x80x9clayer 5 headersxe2x80x9d and higher-numbered headers. Traditional routers only look at layer 3 headers in a message; the new breed of routers will, by contrast, base their forwarding decision on layer 3, layer 4, and even higher layer headers.
Layer 4 switching offers increased flexibility for customers. It allows traffic from dangerous external sites to be blocked, allows bandwidth to be reserved for traffic flowing between two company sites in different parts of the country, and it allows important traffic (e.g., database lookups) to be given preferential treatment when compared to less important traffic (e.g., Web browsing). Layer 4 switching allows service differentiation because traffic from a host S1 to destination H can be given better treatment when compared to another traffic host S2 to H. Similarly, web traffic to H can be treated differently from, for example, file transfer to H. Traditional routing does not provide service differentiation because all traffic going to a given Internet address H is treated identically.
While providing these advantages, however, layer 4 switching introduces a number of architectural complications. First, a change in higher layer headers will require reengineering of routers that have traditionally looked at only layer 3 headers. Second, with encrypted higher layer headers for security, it is not clear how routers can get access to higher layer headers.
Despite these problems, various species that fall under the genus of layer 4 switching have already evolved in the industry. First, many routers at trust boundaries, such as the entry and exit points of corporations, implement so-called xe2x80x9cfirewallsxe2x80x9d. A firewall database consists of a series of filters on packet headers that implement security policies. A typical policy may be to allow remote login that originates within the corporation but to disallow remote login that originates outside the corporation. Second, the need for predictable and guaranteed service has lead to proposals for filters, for instance, to reserve certain bandwidth between a source and destination networks. Third, the cries for routing based on traffic type have become more strident recently (e.g., route web traffic between site 1 and site 2 on route A and other traffic on route 2). These examples are illustrated in FIG. 1, which schematically illustrates a network that provides traffic sensitive routing, a firewall rule, and a resource reservation, all of which are implemented in router R. A typical set of rules for router R is shown in tabular form in FIG. 2.
In FIG. 2, the first rule in the table routes video traffic from S1 to D via L1; not shown is the default routing to D which is via L2. The second rule blocks traffic from an experimental site S2 from accidentally leaving the site. The third rule reserves 50 MBPS of traffic from an internal network X to an external network Y, implemented perhaps by forwarding such traffic to a special outbound queue that receives special scheduling guarantees. In FIG. 2, X and Y are xe2x80x9cprefixes,xe2x80x9d as defined below.
The major problem that traditional routers face in forwarding an Internet message relates to the process of xe2x80x9caddress lookup.xe2x80x9d FIG. 3 is a block diagram of a hypothetical fragment of the Internet linking users in Europe with users in the United States. Consider a source user xe2x80x9cSourcexe2x80x9d in Paris. If this user wishes to send, for example, an email message to San Francisco, the user will send its message to a router R1 which is, for example, in Paris. The Paris router may send this message on the communication link L4 to router R, which may be in London. The London router R may then send the message on link L2 to router R3 in San Francisco; router R3 then sends the message to the destination.
This example shows that a message travels from source to destination alternating between communication links and routers in a manner analogous to the way a postal letter travels from post office to post office using some transportation channel (e.g., an airplane). In the case of a postal letter, each post office decides where to forward the letter in accordance with the destination address that is placed on the envelope containing the letter. In a similar manner, routers must decide to forward a message based on a xe2x80x9cdestination addressxe2x80x9d that is placed in an easily accessible portion of the message called a header.
Let us now consider how a traditional router forwards an incoming message by referring to the router R shown in FIG. 3. We show a schematic description of router R in FIG. 4. When a message arrives on link L4, for example, the message carries its destination address SanFrancisco in its message header. Router R is a special computer whose job is to forward all messages that are sent to it towards their final destinations. To do so, router R consults a xe2x80x9cforwarding tablexe2x80x9d (sometimes also called a xe2x80x9cforwarding databasexe2x80x9d). This is a table in the memory of R, which could list each possible destination and the corresponding output link. Thus, when a message to San Francisco arrives on link L4, router R looks up the destination address SanFrancisco in its forwarding table. Since the table says xe2x80x9cL2,xe2x80x9d the router then switches the entire message to the output link L2. It then proceeds to service the next arriving message.
Address lookup and message switching must both be done at very high speeds. The problem of message switching has become very well understood in recent years because of advances in ATM Switching Technology. On the other hand, the problem of address lookup remains difficult because Internet routers store address prefixes in their forwarding tables to reduce the size of their tables. For example, instead of storing every possible address in the United States in a table, router R of FIG. 4 could be configured to store a smaller number of prefix entries, such as USA.CA.SanFrancisco- greater than L2, USA.CA.*- greater than L3, and USA.*- greater than L1, if these were the only rules needed for a particular router. (For readability, routing rules such as those of this example are sometimes presented symbolically in this specification.) However, the use of address prefixes such as USA.CA.* and USA.* makes the lookup problem one of longest matching prefix instead of exact matching. The longest matching prefix problem is considerably more difficult. The current Internet (IPv4, for Internet Protocol, version 4) uses addresses that are bit strings of length 32. The next generation Internet (IPv6, for Internet Protocol, version 6) will use 128 bit addresses. The longer length of IPv6 addresses will only compound the problems of routers.
As a simple example of how a destination address is matched to an entry in a table in a typical prior art router, consider a sample forwarding table of Internet address prefixes such as that shown in FIG. 5. This table will be used, with minor variations, for all of the examples presented herein.
A typical prior art router first extracts the destination Internet address D from the message and finds the longest prefix P in its database that matches D. The router then switches the message to the output link associated with D. Suppose a message to be routed has a 32 bit IPv4 destination address in which the first 6 bits are 101010. The best matching prefix for an IP lookup is the longest matching prefix. Referring to FIG. 5, the best matching prefix is clearly prefix P4, although the first six bits of the destination address also matches prefix P1. Thus any message to such a destination address should be sent to the output link corresponding to P1 (not shown in FIG. 5).
Although routers can use tables such as that shown in FIG. 5 to determine which output link should be used to route a message, traditional routers cannot distinguish between different kinds of traffic going to the same address D. For example, casual web surfing to address D may be far less important than access to a company database at address D. A network manager may wish to give the latter traffic different service (e.g., more bandwidth, less congested routes) than the former. Level 4 switching achieves this differential service by replacing the lookup method used in traditional routers (a best matching prefix lookup on the destination address field) by a more complex lookup method (a best matching filter lookup on a combination of various fields in the message including the destination address, source address, and application classifier fields). Except for this change in the lookup method, the rest of the process remains similar. As before, there is an output link associated with the best matching filter and, as before, the message is switched to that output link. However, in addition, there are two more pieces of information associated with the filter. First, there may be a xe2x80x9cblockxe2x80x9d characteristic associated with the filter that will cause the message to be blocked; this association is useful in implementing firewalls. Second, there may be a specification of an output queue for the corresponding output link; this specification can be used to reserve bandwidth for certain types of packets.
Making the lookup depend on other fields (especially fields that describe the type of application sending the message) permits differential service to be provided to different types of traffic. For example, both TCP and UDP protocols identify destination and source port numbers. For example, most electronic mail uses a protocol known as SMTP where mail is sent to destination port 25. Most file transfers use a protocol known as FTP that is often sent to destination ports 20 and 21. By far the most common application, the World Wide Web, most often sends messages to destination port 80 (or less commonly to easily recognized substitutes like 81, 800, 8000, or 8080). These port numbers can be thought of as being analogous to telephone extensions. Thus, within a given Internet computer D that is has a given Internet destination address, the destination port represents an xe2x80x9cextensionxe2x80x9d of a process within D that should receive a message. Similarly, for a message sent by a source computer S, a source port represents an xe2x80x9cextensionxe2x80x9d of a process within S that sent the message. Analogous to the way different departments (e.g., shipping, billing, and ordering) may be assigned to different extension numbers within a company and provided with differential levels of telephone service, differential service might be provided to network messages, depending upon the port number to which they are addressed, the port number from which they are received, or both. Thus, a simple way to give preference to electronic mail over Web traffic, for example, would be to give more bandwidth to messages sent to port 25 than to port 80. Similarly, replies sent from port 80 could be given reduced priority compared to other traffic. A few of the many other possibilities for providing differential service include distinguishing TCP from UDP and TCP-ACK (TCP acknowledgement) traffic via the protocol field, and recognizing different source addresses to give preferential treatment to traffic depending upon where it originated.
In general the decision on how to forward a message can depend on several fields in the message. Each combination of fields that a manager (or some routing protocol) decides requires special treatment needs to be specified by a rule or a filter. Any fields that are irrelevant in a rule can be wildcarded (i.e., using a don""t care character which is traditionally the xe2x80x98*xe2x80x99).
In most firewall implementations, the rules are listed in a database in some order; the cost of a rule is the position in the order. Thus the lowest cost rule is the first rule in the database that matches the message. In the general level 4 switching problem, there may be a more general notion of cost.
A level 4 router database comprises N rules or xe2x80x9cfiltersxe2x80x9d R1 . . . RN. Each rule R is an array of K distinct fields, where R[i] is a bit string. Each field i in a rule is allowed three kinds of matches (although further generalizations are possible to allow more flexibility, it is preferred to keep the examples cited herein as simple as possible while remaining realistic): the field could specify an exact match (for example with the flags field); the field could specify a prefix match (useful especially to block accesses from certain subnetworks that have a common prefix); and finally the field could specify a range match (useful especially to specify ranges of port numbers to block or pass).
More general match capabilities can be specified using a set of bit or symbol values. For example, a filter in a router might specify that only messages to or from even numbered port numbers be forwarded. This forwarding rule would be tedious to specify using only ranges or prefixes, but is easy to specify using rule sets. As will be recognized by those skilled in the art, the invention described in this disclosure easily generalizes to handle arbitrary bit or symbol sets.
Each rule Ri has an associated disposition dispositioni that describes how to forward a matching message. Each disposition may specify that the message be passed or blocked; if it is to be passed it must also specify an outgoing link, and (possibly) a queue within that link for bandwidth reservations. In a firewall configuration, the only interesting value of the disposition associated with a filter/rule is whether the specified traffic type should be allowed or blocked.
Field i of a rule R is defined as matching a packet P if either: a) field i specifies an exact match and R[i]=P[i]; b) field i specifies a prefix match and R[i] is a prefix of P[i]; c) field i specifies a range match and P[i] is in the range specified by R[i], or d) field i specifies a set match and P[i] is in the set specified by R[i]. (The examples herein deal primarily with ranges and prefixes, but easily generalize to set matches.) It is known in the art that range matches and exact matches can be converted into prefix matches, and that longest matching prefix matches are more efficient than range matches. A range match can be converted into a prefix match by adding a small number of extra rules in place of a rule that contains a range match. Any arbitrary range can be rewritten as the union of several prefix ranges. A xe2x80x9cprefix rangexe2x80x9d is a range that can be expressed by a prefix. For example, for 4 bits, the prefix 10* expresses the range [1000, 1011]=[8,11]. Thus, the range [8,12] can be expressed as the combination of the two prefix ranges 10* and 1100. However, in some important cases, as in the case of destination and source port numbers of 16 bits, it is easy to do range matches using an array of 216 elements that maps each possible port number to its corresponding range match.
It is easy to convert a set of N filters with overlapping ranges to an equivalent set of 2N filters with non-overlapping ranges. For example, consider 3 filters that have only destination ports specified. Filter F1 specifies a range 1 . . . 5, Filter F2 specifies a range 2 . . . 3 and Filter F3 specifies a range 3 . . . 4. Since the three original ranges overlap, these can be rewritten as a set of 4 non-overlapping ranges: 1 . . . 2, 2 . . . 3, 3 . . . 4 and 4 . . . 5. Filter F1 then needs to be rewritten as 4 equivalent filters; Filter F2 and F3 remain unchanged. In the worst case, rewriting filters in this way can add more filters than when one converts all ranges to prefixes. It is an implementation choice whether to convert naively to non-overlapping ranges or convert to prefix ranges.
A packet P is defined as matching rule R if for all K packet fields P[i] matches field i in rule R. The packet filtering problem is defined as finding the first (i.e., the rule Ri with the smallest value of i) rule that matches a given packet P and to forward the message according to the manner specified in dispositions.
Finding the first matching rule is important because packet headers can match multiple rules. Default rules (such as xe2x80x9cblock everything not specifiedxe2x80x9d) are specified at the end. It is not acceptable for a filtering implementation to reorder the rules for improved performance. (See B. Chapman et al., Building Internet Firewalls, O""Reilly and Associates, November, 1995.) Consider again the table shown in FIG. 5, which was considered in an earlier IP lookup example. For an IP lookup of an address having 101010 as the first six bits, the best match is defined in terms of the longest length. Thus, the filter having IP address prefix P4 is the best match for an IP lookup. However, other types of filters, the best match may be defined in terms of a lowest cost match (where the cost may be set by a manager) or the first filter matched. Firewalls (such as in the examples presented in Chapman) pick the first filter in the database that matches, assuming that the filters are entered in some specified order by the manager. Thus, in a firewall, the best match in the table of FIG. 5 to an address having 101010 as the first six bits is the filter having IP address prefix P1, even though address prefix P4 is a longer match.
Existing implementations of firewalls do a linear search of the firewall rule set until a match is found. Some implementations also cache full packet headers to speed up the processing in some cases. Caching of even just destination addresses has been found to have at most a 90 percent hit rate (P. Newman, et al., xe2x80x9cIP switching and gigabit routers, xe2x80x9cIEEE Communications Magazine, January 1997), however, and the cost of linear searching in the remaining 10 percent of the cases is high. It would therefore be advantageous if faster devices and methods for searching a database having the characteristics of a rule set for a router or firewall were available. It would be especially desirable if such devices and methods were capable of providing increased flexibility for routing, including the capability of differential handling of traffic at high traffic loads.
It is therefore an object of the invention to provide devices and methods for rapidly routing data packets through a router, including a firewall.
It is a further object of the invention to provide devices and methods for rapidly solving the problem of finding a best matching filter for a data packet.
It is yet another object of the invention to provide devices and methods for providing increased flexibility for routing data packets through a router.
It is still another object of the invention to provide devices and methods for the differential handling of message traffic in digital networks at high traffic loads.
It is a still further object of the invention to provide devices and methods for rapid IP lookup in applications such as Internet routing.
In accordance with one aspect of the invention, there is thus provided a method for routing a data packet applied to an input port of an electronic router, the data packet including routing information comprising at least a destination address field containing a destination address, and the electronic router having a plurality of outputs each corresponding to an output data link, and a routing database including filter entries each having a corresponding cost and an associated output data link, said method comprising the steps of: a) operating the router to perform a crossproducting search on the routing information included in the data packet to find a least-cost matching filter in the routing database and its corresponding output data link; and b) routing the data packet to an output of the router corresponding to the output data link found in the crossproducting search.
When the routing information comprises a plurality of routing fields including the destination address field; the routing database comprises a plurality of sub-databases and a crossproduct database, each sub-database corresponding to a different routing field of a data packet and including prefix filters encompassing all possible values of a routing field corresponding to the sub-database; and the crossproduct database comprises a database of output data links corresponding to crossproduct terms of prefixes contained in the crossproduct database, operating the router to perform the crossproducting search may comprise: searching for one of a longest matching prefix or a narrowest enclosing range for each routing field in the data packet in sub-databases corresponding to the routing fields, each search producing a search result; concatenating the search results into a crossproduct term; and searching for an output link corresponding to the crossproduct term in the crossproduct database.
A further refinement of the above method includes the steps of determining whether the search for the output link corresponding to the crossproduct term fails to find an output link; if no output link was found, computing an earliest matching filter associated with the crossproduct term; and associating an output link corresponding to the earliest matching filter found in the computing step with the crossproduct term in the crossproduct database.
There are also provided additional optimizations of the above methods including an early stopping optimization to reduce storage requirements, and methods of caching crossproducts to provide enhanced speed.
Also provided, in accordance with another aspect of the invention, is a routing system for data packets having a plurality of fields, the routing system comprising: a plurality of input data links for receiving incoming data packets; a plurality of output data links for dispatching outgoing data packets; a switch interconnected between said input data links and said output data links and adapted to selectively connect one of said input data links to one of said output data links; and a data processor coupled to said adjustable switch and having means for controlling said switch, said data processor including a database of filters each having an associated filter cost, and each of said filters having a prefix on a set of selected packet fields and an association with an output data link for routing an incoming data packet, said data processor also including means for accessing said database for matching of data packet fields with said filters in said database, said means for controlling said switch being responsive to a match of said data packet fields with one of said filters in said database to thereby route a data packet received at an incoming data link to a corresponding output data link. The accessing system of the routing system may include means for performing a crossproducting search to match fields in a received data packet with an earliest matching filter.
Also provided in accordance with other aspects of the invention and described in detail herein are methods for creating databases for routing data packets, including one such method in which a plurality of arbitrary filters are provided, each comprising one of a prefix or non-overlapping range for each field of the data packets to be searched, so that each of the prefixes or non-overlapping ranges becomes a filter specification, and each of the filters further comprises an output link specification. The method comprises the steps of: placing all of the filter specifications for the fields of the data packets corresponding to each filter in sub-databases corresponding to each field of the data packets, building each sub-database corresponding to each field of the database into a query-matching database having query-matching entries; matching fields of received data packets to entries in the sub-database to generate crossproducts from the query-matching entries; and caching a set of most recently generated crossproducts.
The invention in all of its various aspects will be better understood by those skilled in the art with reference to the detailed description below and the accompanying drawings.